class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def maxPathSumCore(self, root: TreeNode, sum_list):
        if root.left is None and root.right is None:
            sum_list.append(root.val)
            return root.val, -65536
        left_var = -65536
        right_val = -65536
        left_turn = -65536
        right_turn = -65536
        if root.left != None:
            left_var, left_turn = self.maxPathSumCore(root.left, sum_list)
        if root.right != None:
            right_val, right_turn = self.maxPathSumCore(root.right, sum_list)
        sum_list.append(root.val)
        run_list = [root.val, left_var + root.val, right_val + root.val]
        static_run = sum_list + [left_var + right_val + root.val, left_turn, right_turn, left_var, right_val]
        return max(run_list), max(static_run)
    
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        sum_list = []
        return max(self.maxPathSumCore(root, sum_list))
        # return max(sum_list)


def build_tree(tree_list):
    # [-10, 9, 20, None, None, 15, 7]
    # [1, -2, -3, 1, 3, -2, null, -1]
    i = 0
    root = TreeNode(1)
    root.left = TreeNode(-2)
    root.right = TreeNode(-3)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(3)
    root.right.left = TreeNode(-2)
    root.left.left.left = TreeNode(-1)
    return root


def main():
    sol = Solution()
    root = TreeNode(-6)
    left = TreeNode(3)
    right = TreeNode(2)
    root.left = left
    left.right = right
    print(sol.maxPathSum(build_tree([])))


if __name__ == "__main__":
    main()
